package cn.bellychang.leetcode.question212;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author ChangLiang
 * @date 2021/3/17
 */
public class Solution {

    public List<String> findWords(char[][] board, String[] words) {


        List<String> result = new ArrayList<>();

        int row = board.length;
        if (row == 0) {
            return result;
        }
        int col = board[0].length;
        if (col == 0) {
            return result;
        }

        Tire tire = new Tire();
        for (String word : words) {
            tire.insert(word);
        }

        Set<String> set = new HashSet<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                findWord(board, tire, "", i, j, set);
            }
        }
        return new ArrayList<>(set);
    }

    private void findWord(char[][] board, Tire tire, String parent, int i, int j, Set<String> set) {
        if (i < 0 || i == board.length || j < 0 || j == board[0].length) {
            return;
        }
        if (tire.size == 0) {
            return;
        }
        char c = board[i][j];
        if (c == '.') {
            return;
        }
        Tire child = tire.children[c - 'a'];
        if (child != null) {
            if (child.end) {
                set.add(child.str);
            }
            board[i][j] = '.';
            findWord(board, child, parent, i + 1, j, set);
            findWord(board, child, parent, i - 1, j, set);
            findWord(board, child, parent, i, j + 1, set);
            findWord(board, child, parent, i, j - 1, set);
            board[i][j] = c;
        }
    }

    public static class Tire {
        Tire[] children = new Tire[26];
        boolean end;
        int size = 0;
        String str = "";
        public void insert(String word) {
            insert(word.toCharArray(), 0);
        }

        private void insert(char[] word, int index) {
            if (word.length == index) {
                end = true;
                return;
            }
            Tire tire = children[word[index] - 'a'];
            if (tire == null) {
                tire = new Tire();
                children[word[index] - 'a'] = tire;
                tire.str = new String(word, 0, index + 1);
                size++;
            }
            tire.insert(word, index + 1);
        }
    }
}
